


class Solution:

    def firstMissingPositive(self, nums: list):
        
        n = len(nums)
        if n == 1:
            return 1 if nums[0] != 1 else 2

        for i in range(n):
            # 先判断在不在范围内，再判断在不在位置上
            while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
                j = nums[i] - 1
                nums[i], nums[j] = nums[j], nums[i]
            
        
        for i in range(n):
            if i + 1 != nums[i]:

                return i + 1

        return n + 1 



if __name__ == "__main__":

    nums = [3,4,-1,1]
    sol = Solution()
    ans = sol.firstMissingPositive(nums)
    print(ans)



